package Top_Interview_Questions.Sort;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/22 19:45
 * <p>
 * 功能描述:
 */
public class _0075 {

    public static void main(String[] args) {
        _0075 test = new _0075();
        int[] nums = {2, 0, 2, 1, 1, 0};
        test.sortColors(nums);
    }

    /**
     * 荷兰三色旗问题解
     */
    public void sortColors(int[] arr) {
        int less = -1; // <区的右边界
        int more = (arr.length - 1) + 1; // >区的左边界
        int index = 0;
        while (index < more) { // index是当前数的下标
            if (arr[index] == 0) {  //小于区域
                less++;
                swap(arr, less, index);
                index++;
            } else if (arr[index] == 2) { //大于区域
                more--;
                swap(arr, more, index);
                //因为把当前arr[index]和 >区的左边界的前边的1个值(也就是arr[more])做了交换
                //但是arr[more]还没有被判断过，所以这里index不能+1
            } else {
                index++;
            }
        }
    }

    // for test
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }



    /*--------------------------------------自己写的---------------------------------*/

    /**
     * 0ms,打败100%
     */
    public void sortColors1(int[] nums) {
        int[] count0 = new int[1];
        int[] count1 = new int[1];
        int[] count2 = new int[1];
        for (int k : nums) {
            if (k == 0) {
                count0[0]++;
            } else if (k == 1) {
                count1[0]++;
            } else {
                count2[0]++;
            }
        }
        int i = 0;
        for (int j = 0; j < count0[0]; j++)
            nums[i++] = 0;

        for (int j = 0; j < count1[0]; j++)
            nums[i++] = 1;

        for (int j = 0; j < count2[0]; j++)
            nums[i++] = 2;

    }
    /*------------------------------------------------------------------------------*/
}
